#include <stdlib.h>
#include <limits.h>
#include "memmang.h"
#include "linkedList.h"
#include "nodes.h"

/* -----------------------------------------------------------------

Memory Management Utilities
---------------------------

These are provided to help you build your memory manager. You do not
need to modify the codes given here.

----------------------------------------------------------------- */

extern TMemoryNode *_head;

/* -----------------------------------------------------------------

Memory Allocation Routines
--------------------------

These are the actual routines you will implement. You should modify only
findFreeMemory, NSAlloc and NSFree.

----------------------------------------------------------------- */

// The actual memory to allocate
char _memoryBlock[MEMMANG_MAXSIZE];
unsigned long _allocated_length;

void initializeMemory()
{

	// DO NOT MODIFY THIS CODE

	// Initialize the list of nodes
	createList(256);

	// Initializes the memory manager with a single node consisting of free memory
	// the size of memmang_maxsize, starting at location zero.
	TMemoryNode *myNewNode=newNode(0, MEMMANG_MAXSIZE, 0);
	myNewNode->startAddress=MEMMANG_BASEADDR;
	insertNode(myNewNode);
}

unsigned long NSGetLastAllocLen()
{
	return _allocated_length;
}


/* -------------------------------------------

Modify only code below this line 

------------------------------------------- */

// Pre: requestedLen = # of bytes of memory requested
// Post: Returns pointer to memory management node (TMemoryNode) describing the available memory

TMemoryNode *findFreeMemory(unsigned long requestedLen)
{

	/* TODO: Implement algorithm to locate next free memory block
	using the allocation policy indicated */

	// ENSURE THAT YOUR CODE IS PROPERLY DOCUMENTED!!
	//TMemoryNode* theOne = newNode(0, requestedLen, 0);
	TMemoryNode* nodeInList = _head;
	TMemoryNode* smallestNode= newNode(MEMMANG_BASEADDR, requestedLen, 0); // for BESTFIT
	TMemoryNode* biggestNode= newNode(MEMMANG_BASEADDR, requestedLen, 0); // for WORSEFIT

#if MEMMANG_TYPE==MEMMANG_BESTFIT

	// Search for free memory using best fit policy
	int firstInstance = 0;

	//return node if there is only one node
	if(nodeInList->next == NULL)
		return nodeInList;

	while(nodeInList->next != NULL) {
		// this while loop is to find an empty node that can fit the requestedLen
		while(requestedLen > nodeInList->len || nodeInList->allocated == 1) {
			if(nodeInList->next == NULL)
				break;	
			nodeInList = nodeInList->next;
		
		}
		// if the node that is gotten from the while loop fits the requestedLen exactly, that node is returned
		if(nodeInList->len == smallestNode->len) {
			smallestNode = nodeInList;
			break;
		}
		// this only applies for the first instance an empty fitting node is found
		// store node as smallest for comparisons to be made
		else if(firstInstance == 0){
			smallestNode = nodeInList;
			firstInstance++;
		}
		// comparing this node with the smallest and storing the smallest
		else if(nodeInList->len < smallestNode->len) {
			smallestNode = nodeInList;
		}
		if(nodeInList->next != NULL) {
			nodeInList = nodeInList->next;
		}
	}

	return smallestNode;

#elif MEMMANG_TYPE==MEMMANG_WORSTFIT

	// Search for free memory worst fit policy
	int firstInstance = 0;
	// return node if there is only one node
	if(nodeInList->next == NULL)
		return nodeInList;

	
	while(nodeInList->next != NULL) {
		// this while loop is to find an empty node that can fit the requestedLen
		while(requestedLen > nodeInList->len || nodeInList->allocated == 1) {
			if(nodeInList->next == NULL)
				break;	
			nodeInList = nodeInList->next;
		}
		// this only applies for the first instance an empty fitting node is found
		// store node as biggest for comparisons to be made
		if(firstInstance == 0){
			biggestNode = nodeInList;
			firstInstance++;
		}
		// comparing this node with the biggest and storing the biggest
		else if(nodeInList->len > biggestNode->len) {
			biggestNode = nodeInList;
		}
		if(nodeInList->next != NULL) {
			nodeInList = nodeInList->next;
		}
	
	}

	return biggestNode;

#elif MEMMANG_TYPE==MEMMANG_FIRSTFIT

	// Search for free memory using first fit policy

	// return node if there is only one node
	if(nodeInList->next == NULL)
		return nodeInList;

	// this while loop is to find an empty node that can fit the requestedLen
	while(requestedLen > nodeInList->len || nodeInList->allocated == 1) {
		if(nodeInList->next == NULL)
			break;
		nodeInList = nodeInList->next;
	}
	return nodeInList;

#endif

	// dummy return to suppress compiler errors. Modify to return a pointer
	// to the TMemoryNode memory management node describing the free memory found.


}

// Pre: requestedLen = Amount of memory requested in bytes
// Post: Memory is allocated and address of the start of the memory segment allocated is
//       returned. Return a NULL if there is no more memory to allocate.

void *NSAlloc(unsigned long requestedLen)
{
	// TODO: Implement memory allocation algorithm here, returning address of the
	// memory block allocated, cast as (void *).


	/*
	Implement the memory allocation algorithms as shown in the lecture notes.

	Hint: You can write a single allocation routine for all 3 strategies. The
	strategies differ only in the way that findFreeMemory is implemented.

	*/

	// IMPORTANT: Set the global variable _allocated_length to the number of bytes
	//            of memory you are allocating in this request.

	// Dummy return statement to suppress compiler errors

	// ENSURE THAT YOUR CODE IS PROPERLY DOCUMENTED!!

	TMemoryNode* node = findFreeMemory(requestedLen);
	if(node->allocated == 1) { // no memory
		return NULL;
	}
	unsigned int i=0;
	_allocated_length = requestedLen;
	unsigned long address = node->startAddress;
	unsigned long length = node->len;
	
	if (length > requestedLen) {
		deleteNode(node);
		TMemoryNode* newFirstNode = newNode(address, requestedLen, 1);
		insertNode(newFirstNode);
		//printf("New First Inserted ");

		createList(256);
		//createList is done here because after some time, 
		//_listhead goes out of memory causing ret to be a NULL
		//as a result newNode returns a NULL

		TMemoryNode* newSecondNode = newNode(address+requestedLen,length-requestedLen,0);
		//printf("new Second created");
		insertNode(newSecondNode);	
	}

	else {
		node->allocated = 1;
	}
	return (void *)address;
}

// Pre: pointerToFree = Starting address of memroy segment to free
// Post: Memory segment is freed

void NSFree(void *pointerToFree)
{
	// Implement the free memory routine.
	// Locate the node corresponding to the memory to free, set the allocated flag
	// to false to "deallocate" the memory, and do a merge if possible with neighboring
	// "free memory" nodes.

	// ENSURE THAT YOUR CODE IS PROPERLY DOCUMENTED!!

	TMemoryNode* nodeInList = _head;
	unsigned int i=0;

	while ((unsigned long)pointerToFree != nodeInList->startAddress) {
		nodeInList = nodeInList->next;
	}

	nodeInList->allocated = 0;

	if (testAdjacent(nodeInList)) { 
		mergeNodes(nodeInList);
	} 

	if (testAdjacent(nodeInList->prev)) {
		mergeNodes(nodeInList->prev);
	}

}



